CPU 스케줄링
CPU 이용률을 최대화하여 프로세스를 최대한 많이 실행시키기 위해 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업
🧑🏻💻 기본 개념
✅ CPU 버스트 & I/O 버스트
- 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다.
✏️ CPU 버스트
사용자 프로그램이 직접 CPU를 가지고 빠른 명령어를 수행하는 일련의 단계
✏️ I/O 버스트
I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
✏️ CPU 바운드 프로세스
CPU 버스트가 길게 나타나는 프로세스
✏️ I/O 바운드 프로세스
CPU 버스트가 짧게 나타나는 프로세스
✏️ CPU 스케줄링의 필요성
- 프로세스의 CPU 버스트가 모두 균일하다면 CPU 스케줄링이 큰 의미가 없지만, 우리가 사용하는 시분할 시스템에서는 CPU 버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 필요하다.
✅ CPU 스케줄러
준비 상태에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할지 결정하는 운영체제 코드
- CPU가 유휴 상태가 될 때마다 운영체제는 CPU 스케줄러에 따른 선택 절차를 통해 준비 큐에 있는 프로세스 중 하나를 실행한다.
✏️ 준비 큐
메인 메모리에 상주하며 실행되기를 기다리는 프로세스 집합으로, FIFO 방식의 큐 뿐만 아니라 우선순위 큐, 트리 등 다양한 방식으로 구현 가능하다.
✅ 선점 및 비선점 스케줄링
✏️ CPU 스케줄링이 필요한 경우
- 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
- 프로세스가 종료될 때
✏️ 비선점형 스케줄링
하나의 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스가 CPU를 점유할 수 없는 스케줄링 방식
✏️ 선점형 스케줄링
하나의 프로세스가 CPU를 차지하고 있을 때 우선 순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
✅ 디스패처
새롭게 선택된 프로세스가 CPU를 할당 받고 작업을 수행할 수 있도록 환경 설정을 하는 운영체제 코드
✏️ 디스패처의 역할
- 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
✏️ 디스패치 지연
디스패처가 어떤 프로세스로부터 다른 프로세스로 CPU를 전달하기까지 걸리는 시간
✏️ PCB(Process Control Block)
운영체제가 프로세스를 제어하기 위해 정보를 저장해 놓는 곳으로 프로세스의 상태 정보를 저장하는 구조체
✏️ 문맥 교환(Context Switching)
하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 상태를 적재하는 작업
🧑🏻💻 스케줄링 기준
스케줄링 기법의 성능을 평가하기 위한 지표
CPU 이용률: 전체 시간 중 CPU가 일을 한 시간의 비율처리량: 단위 시간 당 완료된 프로세스의 개수소요 시간: 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합대기 시간: 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합응답 시간: 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
🧑🏻💻 스케줄링 알고리즘
✅ 선입 선처리 알고리즘 (First Come First Served Scheduling, FCFS)
가장 간단한 CPU 스케줄링 알고리즘으로, CPU를 먼저 요청하는 프로세스에게 CPU를 먼저 할당하는 방식
- 비선점형 스케줄링 방식으로, 경우에 따라 비효율적인 결과 초래한다.
콘보이 현상(Convoy effect): CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상
✅ 최단 작업 우선 스케줄링 (Shortest Job First Schduling, SJF)
CPU 버스트 길이가 가장 작은 프로세스부터 순서대로 CPU 할당하는 방식
- 평균 대기시간을 가장 짧게 하는 최적 알고리즘
- 프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에 예측을 통해 CPU 버스트 시간을 계산한다.
- 비선점형, 선점형 방식 모두 가능하다.
✏️ 비선점형 방식
- 준비 큐에 현재 CPU를 할당받은 프로세스보다 CPU 버스트 시간이 더 짧은 프로세스가 도착한다고 해도 CPU를 점유하지 않는다.
✏️ 선점형 방식
- 준비 큐에 CPU 버스트 시간이 더 짧은 프로세스가 도착하면 해당 프로세스가 현재 CPU를 점유하고 있는 프로세스로부터 CPU를 선점한다.
- 중간에 새로운 프로세스가 도착하는 경우가 많은 일반적인 시분할 환경에서는 선점형 방식이 평균 대기 시간을 가장 많이 줄일 수 있는 방식이다.
- 기아 현상(Starvation) 발생 가능
기아 현상(Starvation): CPU 버스트가 짧은 프로세스가 계속 도착할 경우 CPU 버스트가 긴 프로세스는 무한정 대기해야 하는 현상
✅ 우선순위 스케줄링 (Priority Scheduling)
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
- 우선순위는 우선 순위값이 작을수록 높은 우선순위를 가지는 것으로 가정하며, 우선순위를 결정하는 다양한 방식 존재한다.
- 선점형, 비선점형 방식이 모두 존재한다.
- 기아 현상이 발생할 수 있으며 이를 해결하기 위해 노화(aging) 기법 사용 가능하다.
노화(aging) 기법: 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 우선순위가 되어 CPU를 할당받을 수 있도록 하는 기법
✅ 라운드 로빈 스케줄링 (Round Robin Scheduling)
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한하는 방식
- 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식이다.
할당 시간(time quantum): 프로세스가 한 번에 CPU를 사용할 수 있는 최대 시간
- 할당 시간이 너무 길 경우 FCFS와 같은 결과를 도출한다.
- 할당 시간이 너무 짧을 경우 문맥 교환의 오버헤드가 발생한다.
- 일반적으로 할당 시간을 수십 밀리 초 정도의 규모로 설정한다.
- 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.
✅ 멀티 레벨 큐 스케줄링(Multi Level Queue Scheduling)
준비 큐가 프로세스가 존재할 수 있는 여러 개의 큐로 구성되며 각각의 큐마다 다른 우선순위를 배정하는 방식
- 여러 개의 준비 큐에 대해 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링 필요
고정 우선순위 방식: 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스타임 슬라이스(time slice): 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 점유 시간을 적절한 비율로 할당
- 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
✅ 멀티 레벨 피드백 큐 (Multi Level Feedback Queue Scheduling)
- 프로세스를 여러 큐에 나누어 저장한다는 점은 멀티 레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능
- 프로세스에 고정된 우선순위를 부여하는 것이 아니라 각 프로세스의 특성에 따라 동적으로 우선순위를 부여한다.
- 기아 현상을 예방할 노화 기법의 일종으로 구현 가능
- 최상위 큐가 우선적으로 CPU를 할당받고, 상위 큐가 비었을 때에만 하위 큐에 CPU가 할당된다.
- 프로세스의 CPU 작업 시간을 다단계로 분류함으로써 작업 시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 하고, 작업 시간이 긴 프로세스에 대해서는 문맥 교환 없이 FCFS 방식을 채택하도록 한다.
🧑🏻💻 다중 처리기 스케줄링
다중 처리기 시스템(Multi-Processor System): CPU가 여러 개인 시스템- 다중 처리기 시스템에서는 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능하지만 스케줄링 문제는 그에 상응하여 더욱 복잡해짐
✅ 비대칭형 다중 처리
- 하나의 CPU가 모든 스케줄링을 결정하는 방식으로, 병목현상 발생 가능
✅ 대칭형 다중 처리
- 각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스스로 스케줄링을 진행하는 방식
- 각 CPU별 부하가 적절히 분산되도록 하는 부하 균등화(load balancing) 메커니즘 필요
push migration: 특정 태스크가 주기적으로 각 CPU의 부하를 검사하고 만일 불균형 상태라면 바쁜 CPU로부터 쉬고 있는 CPU로 프로세서를 이동시켜 부하 분배pull migration: 쉬고 있는 CPU가 바쁜 CPU를 기다리고 있는 프로세서를 가져옴
🧑🏻💻 실시간 CPU 스케줄링
시분할 시스템과는 달리 데드라인이 존재하는 실시간 시스템에 대하여 CPU를 스케줄링하는 방식
연성 실시간 시스템(Soft Real-Time System): 데드라인을 만족하다는 것을 보장하지 않으며, 중요한 실시간 프로세스가 그렇지 않은 프로세스에 비해 우선권만 가지고 있다.경성 실시간 시스템(Hard Real-Time System): 데드라인을 만족하는 것을 100% 보장한다.
✅ 지연 시간 최소화
이벤트 지연시간: 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간- 데드라인을 만족하기 위해서는 지연 시간을 최소화하는 것이 중요하다.
✏️ 지연 시간의 종류
인터럽트 지연 시간: CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴(ISR)이 시작하기까지의 시간디스패치 지연 시간: 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간
✅ 우선순위 기반 스케줄링 (Priority Based Scheduling)
실시간 시스템의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원하며 각각의 프로세스의 중요성에 따라 우선순위를 부여한다.
- 이와 같은 방식은 실시간 프로세스가 데드라인을 만족한다는 것을 보장하지 못하기 때문에 연성 실시간 시스템에만 적용 가능하다.
- 경성 실시간 시스템을 지원하기 위해서는 부가적인 스케줄링 기법 필요하다.
Rate Monotonic 스케줄링: 각각의 주기 태스크들에 대하여 주기가 짧으면 높은 우선순위를, 주기가 길면 낮은 우선순위를 배정하고 해당 우선순위에 따라 프로세스를 할당한다.Earliest-Deadline-First(EDF) 스케줄링: 각각의 주기 태스크들의 마감 시간에 대하여 마감 시간이 빠르면 높은 우선순위를, 마감 시간이 늦으면 낮은 우선순위를 배정하고 해당 우선순위에 따라 프로세스를 할당한다.